#! /usr/local/cellar/python3/3.6.1/bin
"""组合"""

def combine(n, m):
    combs = []
    combine_inner([0] * m, n, m, n, combs)
    # print("c%d(%d) = %d" % (n, m, len(combs)))
    return combs

def combine_inner(comb, n, m, k, combs):
    """求n个数中取m个数的组合"""
    for i in range(m - 1, k):
        # 当前索引的范围[m-1 ~ k]
        comb[m - 1] = i
        if m > 1:
            combine_inner(comb, n - 1, m - 1, i, combs)
        else:
            combs.append(tuple(comb))

def compute_items(arr, s, m):
    """
    @param arr 要查找匹配的元素的数组
    @param s   m个数求和之后的值
    @param m   arr中要求和的数的个数
    """
    result = []
    combs = combine(len(arr), m)
    for item in combs:
        total = 0
        for i in range(m):
            total += arr[item[i]]
        if total == s:
            result.append(item)
    return tuple(result)

LIST = [10, 2, 3, 22, 11, 24, 1, 25, 29, 40, 30, 34, 21, 20, 5]
print("查找列表的数组：%s" % str(LIST))
print("查找数组中任意三项和为25的匹配项的索引(从0开始)：")
COMBS = compute_items(LIST, 25, 3)
for comb in COMBS:
    print("%s" % str(comb))
print("查找数组中任意两项和为25的匹配项的索引(从0开始)：")
COMBS = compute_items(LIST, 25, 2)
for comb in COMBS:
    print("%s" % str(comb))
